Word break

Time: O(NxL^2); Space: O(N); medium

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Notes:

  • The same word in the dictionary may be reused multiple times in the segmentation.

  • You may assume the dictionary does not contain duplicate words.

Example 1:

Input: s = “leetcode”, wordDict = [“leet”, “code”]

Output: True

Explanation:

  • Return true because “leetcode” can be segmented as “leet code”.

Example 2:

Input: s = “applepenapple”, wordDict = [“apple”, “pen”]

Output: True

Explanation:

  • Return true because “applepenapple” can be segmented as “apple pen apple”.

  • Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]

Output: False

Example 4:

Input: s = “a”, wordDict = [“a”]

Output: True

[1]:

class Solution1(object):
    """
    Time: O(N*L^2)
    Space: O(N)
    """
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        n = len(s)

        max_len = 0
        for string in wordDict:
            max_len = max(max_len, len(string))

        can_break = [False for _ in range(n + 1)]
        can_break[0] = True

        for i in range(1, n + 1):
            for l in range(1, min(i, max_len) + 1):
                if can_break[i-l] and s[i-l:i] in wordDict:
                    can_break[i] = True
                    break

        return can_break[-1]

[2]:

sol = Solution1()

s = "leetcode"
wordDict = ["leet", "code"]
assert sol.wordBreak(s, wordDict) == True

s = "applepenapple"
wordDict = ["apple", "pen"]
assert sol.wordBreak(s, wordDict) == True

s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
assert sol.wordBreak(s, wordDict) == False

s = "a"
wordDict = ["a"]
assert sol.wordBreak(s, wordDict) == True